const climbStairs = function(n){
    if(n < 3) return n;
    let result = 0;
    let pre = 2;
    let prePre = 1;
    for(let i = 3; i <= n; i++){
        result = pre + prePre;
        pre = result;
        prePre = pre;
    }
    return result;
}

const findDisappearedNumbers = function(nums) {
    let n = nums.length;
    for (const num of nums) {
        let x = (num - 1) % n;
        nums[x] += n;
    }
    let result = [];
    for (let i = 0; i < n; i++) {
        if(nums[i] <= n){
            result.push(i+1);
        }
    }
    return result;
};

/**
 * 文斌大大龙
 * 给你一个数组，里面都是不重复的正数，再给定 target，求出所有和为 target 的组合。
 * 元素可以重复使用，但组合不能重复，比如 [2, 2, 3] 与 [2, 3, 2] 是重复的组合。
 *
 *  DFS/回溯/中等难度
 * 回溯算法模板
 * List<Value> result;
 * void backtrack(路径, 选择列表) {
 *     if (满足结束条件){
 *         result.add(路径);
 *         return;
 *     }
 *     for (选择 : 选择列表) {
 *         做选择;
 *         backtrack(路径, 选择路径);
 *         撤销选择;
 *     }
 * }
 *
 */

const combinationSum = function(candidates,target){
    let res = [];
    const dfs = (startIndex, curPath, curSum) =>{
        if(curSum > target){
            return;
        }
        if(curSum === target){
            res.push(curPath.slice());
        }
        for(let i=startIndex; i<candidates.length; i++){
            // 做出当前的选择
            if(candidates[i] > target){
                continue;
            }
            // 做出选择后添加到路径中去
            curPath.push(candidates[i]);
            // 继续递归回溯
            dfs(i,curPath,curSum+candidates[i]);
            // 撤销路径选择
            curPath.pop();
        }
    }
    dfs(0,[],0);
    return res;
}

/**
 *
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用一次。
 */
const combinationSum2 = function(candidates,target){
    let res = [];
    const dfs = (startIndex, curPath, curSum) => {
        if(curSum > target){
            return false;
        }
        if(curSum === target){
            res.push(curPath.slice());
        }
        for (let i = startIndex; i < candidates.length; i++) {
            if(candidates[startIndex] > target){
                continue;
            }
            if(i > startIndex && candidates[i] === candidates[i=1]){
                continue
            }
            curPath.push(candidates[i]);
            dfs(startIndex + 1, curPath, curSum+candidates[i]);
            curPath.pop();
        }
    }
    dfs(0,[],0);
    return res;
}

/**
 * 给定一个没有重复数字的序列，返回其所有可能的全排列。
 * DFS + 回溯 + 中等难度
 */

const permute = function(nums){
    let [res, len] = [[], nums.length];
    const dfs = (curPath) => {
        if(curPath.length === len){
            res.push(curPath.slice());
        }else{
            for (let i = 0; i < len; i++) {
                if(!curPath.includes(nums[i])){
                    curPath.push(nums[i]);
                    dfs(curPath);
                    curPath.pop()
                }
            }
        }
    }
    dfs([]);
    return res;
}

const arrFlat = function(nums){
    let [res, len] = [[], nums.length];
    const dfs = (startIndex, curPath) => {
        if(startIndex === len){
            res.push(curPath.slice());
        }else{
            let arr = nums[startIndex];
            for(let i=0; i < arr.length;i++){
                curPath.push(arr[i]);
                dfs(startIndex+1, curPath);
                curPath.pop();
            }
        }
    }
    dfs(0,[]);
    return res;
}

const maxSubArray = function(arr){
    let result = Number.MIN_SAFE_INTEGER;
    let preSum = Number.MIN_SAFE_INTEGER;
    for (let i = 0; i < arr.length; i++) {
        if(preSum <= 0){
            preSum = arr[i];
            result = arr[i];
        }else{
            preSum = preSum + arr[i]
            result = Math.max(preSum, result);
        }
    }
    return result;
}

/**
 * 旋转数组
 * 文斌大大龙 20
 */
const spiralOrder = function(matrix){
    let res = [];
    let [rows, columns] = [matrix.length, matrix[0].length];
    // top,left,right,bottom分别是剩余区域的上、下、左、右的下标
    let [left,right,top,bottom] = [0, columns-1,0,rows-1];
    // 当前数组长度和长度总和，用来做边界条件的，i,j是循环的临时变量;
    let [count, sum, i, j] = [0, rows*columns,0,0];
    // 从左上角开始，一层一层遍历，每次遍历一圈
    while(count < sum){
        // 这个是上面一个横条（top,left）=> (top,right);
        [i,j] = [top,left];
        while (j <= right && count < sum){
            res.push(matrix[i][j]);
            count++;
            j++;
        }
        // 这是右边竖条 (top+1,right) => (bottom,right);
        [i,j] = [top + 1, right];
        while (i <= bottom && count < sum){
            res.push(matrix[i][j]);
            count++;
            i++;
        }
        // 这是下面一个横条 (bottom,right-1) => (bottom,left);
        [i,j] = [bottom,right -1];
        while (j >= left && count < sum){
            res.push(matrix[i][j]);
            count++;
            j--;
        }
        // 再从下往上走到顶部
        [i,j] = [bottom -1,left];
        while (i > top && count < sum){
            res.push(matrix[i][j]);
            count++;
            i--;
        }
        // 一圈结束开始进入下一圈
        [top,left,bottom,right] = [top+1,left+1,bottom-1,right-1];
    }
    return res;
}

/**
 * 跳跃棋游戏
 * 给定一个非负整数数组，最初位于数组的第一个位置。数组中的每个元素代表在该位置可以跳跃的最大长度。
 * 判断是否能够到达最后一个位置。
 * 基本思路
 *
 * 如果某一个作为 起跳点 的格子可以跳跃的距离是 n，那么表示后面 n 个格子都可以作为 起跳点。
 * 可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离maxJump 不断更新。
 * 如果可以一直跳到最后，就成功了。如果中间有一个点比 maxJump 还要大，说明在这个点和 maxJump 中间连不上了。
 *
 */

const canJump = function(nums){
    let len = nums.length;
    if(len === 1){
        return true
    }
    let curJumpMaxLen = 0;
    for (let i = 0; i < nums; i++) {
        if(i > curJumpMaxLen){
            return false;
        }else{
            curJumpMaxLen = Math.max(curJumpMaxLen,i + nums[i]);
        }
    }
    return true;
}

/**
 * 合并区间
 * 合并给的多个区间，区间有重叠的要进行区间合并。
 */

const mergeArr = function(intervals){
    const [mergedRes, len] = [[], intervals.length];
    // 按照左端点排序，并取开头的第一个区间，作为开始比较的数组;
    intervals.sort((a,b) => a[0] - b[0]);
    let start = intervals[0];
    for (let i = 1; i < len; i++) {
        //取当前区间
        let curInterval = intervals[i];
        // 如果发现开始节点右端大于当前节点左端
        if(start[1] >= curInterval[0]){
            // 那么就把右边的端点设置成较大的有边界
            start[1] = Math.max(start[1], curInterval[1]);
        }else{
            // 不重合，就是断了，那么把开始的节点推入结果数组
            mergedRes.push(start);
            start = curInterval;
        }
    }
    mergedRes.push(start);
    return mergedRes;
}
/**
 * 区间插入算法
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
 *
 * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
 */

const insertArr = function(intervals, newInterval){
    // 插入新的区间;
    intervals.push(newInterval);
    // 新区间长度，做排序
    const [mergeRes, len] = [[],intervals.length];
    intervals.sort((a,b) => a[0] - b[0]);
    let start = intervals[0];
    // 然后从区间起点小的开始扫描，依次合并两个有重叠的区间。
    for (let i = 1; i < len; i++) {
        // 取当前区间
        let curInterval = intervals[i];
        if(start[1] > curInterval[0]){
            start[1] = Math.max(start[1], curInterval[1]);
        }else{
            mergeRes.push(start);
            start = curInterval;
        }
    }
    mergeRes.push(start);
    return mergeRes;
}

/**
 * LeetCode38 数组并集
 *给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，
 * 其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。
 * 每个区间列表都是成对 不相交 的，并且 已经排序 。
 *
 */
const intervalIntersection = function(firstList, secondList){
    const [intersectionsRes, Alen, Blen] = [[], firstList.length, secondList.length];
    let i = 0, j = 0;
    while (i < Alen && j < Blen){
        // start 代表交集区间的左右两端
        // 交集区间的左端，取他们左端点的较大者
        // 交集区间的右端，取他们右端点的较小者
        let start = Math.max(firstList[i][0],secondList[j][0]);
        let end = Math.min(firstList[i][1],secondList[j][1]);
        if(start < end){
            intersectionsRes.push([start,end]);
        }
        if(firstList[i][1] < secondList[i][1]){
            i++;
        }else{
            j++;
        }
    }
    return intersectionsRes;
}

/**
 * leetcode 60
 * 给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
 *
 * 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
 *
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * 给定 n 和  k，返回第 k 个排列。
 */

const getPermutation = function(n,k){
    let usedSet = {};
    let permuteCounts = 1;
    // 一共有permuteCounts组排列组合 n!
    for(let i=1;i<=n;i++){
        permuteCounts = permuteCounts * i;
    }

    const permute = (curPath) => {
        const curLen = curPath.length;
        // 以当前的curPath来看，一个分组的数字个数，之后用k来比较
        permuteCounts = permuteCounts / (n - curLen);
        if(curLen === n){
            return curPath.join("");
        }
        for(let i=1;i<=n;i++){
            if(usedSet[i]){
                continue;
            }
            // 如果当前K大于一组的个数，说明当前不在这组内，直接减去一组的个数，并跳过本次循环
            if(k > permuteCounts){
                k = k - permuteCounts;
                continue;
            }
            curPath.push(i);
            usedSet[i] = true;
            // 本轮确认好了，其实就是确认好了组，进入下一轮
            return permute(curPath);
        }
    }
    return permute([]);
}

/**
 * 文斌大大鸟 23
 * leetcode 61
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 */
const rotateRight = function(head, k){
    if(head === null || head.next === null || k===0){
        return head;
    }
    // oldTail 是起初链表的末尾，我们经过循环
    // 1. 得到链表的长度，注意指到头时 len 已经是 1;
    let  oldTail = head, len = 1;
    while (oldTail.next !== null){
        oldTail = oldTail.next;
        len++;
    }
    //2. 把原末尾接到头上，形成环
    oldTail.next = head;
    //现在的尾应该是（n- k%n -1）个节点位置，头就是尾的下一个位置
    //为社么要使用取模运算？ k > len时，去掉原地转圈 len / k 的整数部分
    //只考虑 k%n的部分，这个值一定比 len 小。
    let nowTail = head;
    for(let i = 0; i < len - k % len - 1; i++){
        nowTail = nowTail.next;
    }
    let nowHead = nowTail.next;
    //将环断开，现在尾部指向null;
    nowTail.next = null;
    return nowHead;
}

/**
 * 文斌大大龙 24
 * leetCode 62 不同路径
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 * 问总共有多少条不同的路径？注意这题是不能往左往上走的
 *
 * 动态规划
 * 动态规划基本步骤
 * 1. 寻找最有子结构
 * 2. 归纳状态转移方程
 * 3。 便捷初始化
 */

const uniquePaths = function(m,n){
    // 生成一个 m * n 的二维数组 dp
    let dp = new Array(m).fill(0).map(item => new Array(n).fill(0));
    // 初始化边界， dp(i,0) 和 dp(0,j) 都为1；
    for (let i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (let j = 0; i < n; j++) {
        dp[0][j] = 1;
    }
    for (let i = 1; i < m; i++) {
        for (let j = 0; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    // (m-1),(n-1)是右下角
    return dp[m-1][n-1];
};


const uniquePathsObstacles = function(obstacleGrid){
    // 起点就是障碍物，直接没有路径 return 0;
    if(obstacleGrid.length === 0 || obstacleGrid[0][0] === 1){
        return 0;
    }
    let [m,n] = [obstacleGrid.length,obstacleGrid[0].length];
    let dp = new Array(m).fill(0).map(item => new Array(n).fill(0));
    // 初始化边界
    dp[0][0] = 1;
    for (let i = 1; i < n; i++) {
        // 第一行只看左边一条，看上一个位置dp[0][i-1] 是否是0 和 当前是否是障碍物
        if(dp[0][i-1] !== 0 && obstacleGrid[0][i] !== 1){
            dp[0][i] = 1;
        }
    }
    for (let j = 1; j < m; j++) {
        // 第一列，只有上面来，看上一个位置dp[j-1][0]是否是0 和 看当前位置是否是障碍物
        if(dp[j-1][0]!== 0 && obstacleGrid[j][0] !== 1){
            dp[j][0] = 1;
        }
    }
    // 再循环遍历，并绕开障碍， obstacleGrid[i][j] !== 1;
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            if(obstacleGrid[i][j] !== 1){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
    }
    return dp[m-1][j-1];
};

/**
 * 最小路径和
 * 文彬大大龙龙 25
 * leetCode 64题目
 *
 * 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，
 * 使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。
 *
 */

const minPathSum = function(grid){
    let [row, col] = [grid.length, grid[0].length];
    // 可以直接再原来的数组上做原地dp,不需要外空间
    // 通过吧边界先加和，左边只能从上走，上边只能从左走；
    for (let i = 1; i < col; i++) {
        grid[0][i] += grid[0][i-1];
    }

    for (let j = 1; j < row; j++) {
        grid[row][0] = grid[row-1][0];
    }

    for (let i = 1; i < row; i++) {
        for (let j = 1; j < col; j++) {
            grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1])
        }
    }
    return grid[row-1][col-1];
};

/**
 * 文斌大大龙 25
 *  LeetCode 66 加一
 *
 *  给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
 *  最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
 *
 */

const plusOne  = function(digits){
    const len = digits.length;
    for (let i = len - 1; i >= 0; i--) {
        digits[i]++;
        // 看最后一位 % 10 是否为 0 如果 为 0 说明有进位
        digits[i]  = digits[i] % 10;
        if(digits[i] !== 0){
            return digits
        }
    }
    digits = new Array(len - 1).fill(0);
    digits[0] = 1;
    return digits;
};

/**
 * 文斌大大龙 27
 * LeetCode 37 爬楼梯
 * 其实是一个斐波那契数列
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * 注意：给定 n 是一个正整数。
 */

const climbStairs2 = function(n){
    let dp = new Array(n).fill(0);
    dp[0] = 1;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i-2] + dp[i-1];
    }
    return dp[n];
};

/**
 * 文斌大大龙 28
 * LeetCode 71
 *
 * 给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格
 * 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径
 *
 */

const simplifyPath = function(path){
    const stack = [];
    const pathArr = path.split('/');
    pathArr.map(item => {
        if(item === '' || item === '.'){

        }else if(item === '..'){
            stack.pop();
        }else{
            stack.push(item);
        }
    });
    return '/' + stack.join('/');
}

/**
 * 文斌大大龙 28
 * LeetCode 73
 * 矩阵置零
 */

const setZeros = function(matrix){
    let [row, col] = [matrix.length, matrix[0].length];
    let rowSet = new Set();
    let colSet = new Set();
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if(matrix[i][j] === 0){
                rowSet.add(i);
                colSet.add(j);
            }
        }
    }
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if(rowSet.has(i) || colSet.has(j)){
                matrix[i][j] = 0;
            }
        }
    }
    return matrix;
}

/**
 * 文斌大大龙 29
 * leetCode 74 搜索二维矩阵
 *
 * 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 *
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 */

// 知识点 数组拍平
// 手动实现一层数组拍平

const flat = function(arr){
    return [].concat(...arr);
};

// 手动实现无限层flat
const flatDeep = function(arr, d=1){
    if(d > 0){
        return arr.reduce((arr, cur)=> arr.concat(
            Array.isArray(cur) ? flatDeep(cur, d-1) : cur
        ), []);
    }else{
        return arr.slice();
    }
};

/**
 * 解题步骤
 * 1. 先拍成一维数组
 * 2. 再二分查找
 */
const searchMatrix = function(matrix, target){
    const matrixFlat = matrix.flat(Infinity);
    let [left, right, mid] = [0, matrixFlat.length - 1, 0];
    while (left < right){
        mid = Math.floor((left + right) / 2);
        if(matrixFlat[mid] === target){
            return true;
        }
        if(matrixFlat[mid] > target){
            right = mid - 1;
        }else{
            left = mid + 1;
        }
    }
    return false;
};

/**
 * 文斌大大龙 29
 * LeetCode 第75题 颜色分类
 * 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 *
 * 我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。
 * 必须在不使用库的sort函数的情况下解决这个问题。
 *
 *  采用计数排序的方式来实现算法
 */
const sortColor = function(nums){
    // 这一题桶是一定的就3个数字，桶里面元素表示这3个数出现的次数
    let [len, cur] = [nums.length,0];
    let bucket = new Array(3).fill(0);
    // 核心就是用index来对应这三个数
    nums.map(item => bucket[item]++);
    // 放回原数组
    for (let i = 0; i < 3; i++) {
        while (bucket[i] > 0){
            nums[cur++] = i;
            bucket[i]--;
        }
    }
    return nums;
};

/**
 * 文斌大大龙 30
 * LeetCode 第76题 最小覆盖子串
 * 给你一个字符串 s 、一个字符串 t 。
 * 返回 s 中涵盖 t 所有字符的最小子串。
 * 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 *
 * 解题方法  滑动窗口的思想
 *
 * 基本步骤
 * 1. 我们首先确定这个滑动窗口满足的条件： 窗口子串内含有t的所有字符，注意可能有重复字符，所以不能用排序等粗暴的办法，
 *      我们建立一个Map，key表示字符，value表示出现的次数
 *      使用curLessKeysLen来表示当前还需要匹配的字符串种类
 *      那么满足条件就是 curLessKeysLen === 0 表示全部都匹配了
 * 2. 滑动右指针扩大窗口，直到满足条件，记录下最优解
 * 3. 此时，我们停止增加right，转而不断增加left缩小窗口，直到窗口中的字符串不再符合要求，同事每次增加left，都要更新一轮结果
 * 4. 重复第2,3步，直到right达到字符串的尽头
 */

const minWindow = function(s, t){
    let [res, left, right, len] = ["", 0, 0, s.length];
    let needMap = new Map();
    t.split("").map(item => {
        if(needMap.has(item)){
            needMap.set(item, needMap.get(item) + 1);
        }else{
            needMap.set(item,1);
        }
    });
    // 当前剩余还需要匹配的字符种类
    let curLessKeysLen = needMap.size;
    // 开始滑动窗口
    while (right < len) {
        let curR = s[right];
        if(needMap.has(curR)){
            // 包含近窗口，needMap对应元素 -1
            needMap.set(curR, needMap.get(curR) - 1);
            if(needMap.get(curR) === 0){
                curLessKeysLen -= 1;
            }
        }
        // 当前需要匹配字符串长度为0，说明当前窗口已满足要求
        while (curLessKeysLen === 0){
            let curL = s[left];
            let nowStr = s.slice(left, right + 1);
            if(res === "" || res.length > nowStr.length){
                res = nowStr;
            }
            // 下面该移动左边框了， 左移动needMap要随之改变
            if(needMap.has(curL)){
                needMap.set(curL, needMap.get(curL) + 1);
                if(needMap.get(curL)  === 1){
                    curLessKeysLen += 1;
                }
            }
            left++;
        }
        right++;
    }
    return res;
};

/**
 * 文斌大大龙算法【31】期
 * LeetCode 第77题
 *
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 *
 * 解题思路 DFS + 回溯算法
 */

const combineFunc = function (n,k) {
    let [res, curUsed] = [[], new Map()];
    let nArray = new Array(n).fill(0).map((item,idx) => idx + 1);
    let dfs = (startIndex,curPath) => {
        if(curPath.length === k){
            res.push(curPath.slice());
            return
        }
        for(let i=startIndex; i<n;i++){
            if(curUsed.get(nArray[i]) === true){
                continue
            }
            curPath.push(nArray[i]);
            curUsed.set(nArray[i],true);
            dfs(i + 1,curPath);
            curPath.pop();
            curUsed.set(nArray[i],false);
        }
    }
    dfs(0,[]);
    return res;
}

/**
 * 文斌大大龙【31】期
 * LeetCode 78 题
 *
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 *
 * 解题思路 DFS + 回溯算法
 */

const subsets = function (nums) {
    let [res, curUsed] = [[], {}];
    let dfs = function (startIndex,curPath){
        res.push(curPath.slice());
        for (let i = startIndex; i < nums.length; i++){
            if(curUsed[i] === true){
                continue;
            }
            curPath.push(nums[i]);
            curUsed[i] = true;
            dfs(i+1,curPath);
            curPath.pop();
            curUsed[i] = false;
        }
    }
    dfs(0,[]);
    return res;
}

/**
 * 文斌大大龙 【31】 期
 * leetcode 第 90 题
 *
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 *
 * 解题思路 DFS + 回溯
 *
 */

const subsetsWithDup = function(nums){
    let [res, curUsed] = [[], {}];
    // 先排序
    nums =nums.sort((a, b) => a - b);
    let dfs = (startIndex, curPath) => {
        res.push(curPath.slice());
        for (let i = startIndex; i < nums.length; i++){
            if(curUsed[i] === true){
                continue;
            }
            // 当前值使用过了
            // 当前值等于前一个值: 两种情况
            // 1. nums[i-1] 没用过 说明回溯到了同一层 此时接着用 num[i] 则会与 同层 num[i-1] 重复
            // 2. nums[i-1] 用过了 说明此时在 num[i-1]的下一层，相等不会重复
            if(i > 0 && nums[i] === nums[i-1] && curUsed[i-1] === false){
                continue
            }
            curPath.push(nums[i]);
            curUsed[i] = true;
            dfs(i+1,curPath);
            curPath.pop();
            curUsed[i] = false;
        }
    }
    dfs(0,[]);
    return res;
}

/**
 * 文斌大大龙第 【32】 期
 *  leetcod 79 题 单词搜索
 *
 *  给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 *
 *  解法思路 DFS + 回溯
 *
 *  解法思路步骤
 *  1. 四个方向上DFS
 *  2. visited数组作用，用来记录已经访问过的位置，以免路径重合
 *  3. 判断走的步骤之后是否越界，是本题的边界条件，说明是在内部走动，形成路径
 *  4. 深刻理解 DFS + 回溯
 */

const matrixExists = function (board, word){
    // 获取 矩阵行、列数和字符串 length
    let [row, col, wordLen] = [board.length, board[0].length, word.length];
    // 取四个方向上走的方式（i,j）坐标  往上走就是i-1 对应 [-1, 0]
    // 右 左 上 下
    const stepDirect = [[0,1],[0,-1],[-1,0],[1,0]];
    // 声明已经访问过的路径，初始化所有的元素为FALSE
    const visited = new Array(row).fill(0).map(item => new Array(col).fill(false));
    // 下面使用DFS，探索正确路径
    let dfs = (i,j,curIndex) => {
        // 如果当前位置正是需要搜索的当前位置，且 curIndex 已经是需要找的最后一个元素，直接返回TRUE
        if(board[i][j] === word.charAt(curIndex) && curIndex === wordLen - 1){
            return true;
        }
        // 如果当前位置不等于我们需要搜索的当前串 curIndex 元素， 返回FALSE
        if(board[i][j] !== word.charAt(curIndex)){
            return false;
        }
        // 走到这步之后，该位置 存入 visited, 表示已经访问过了，要不绕回到原点就有问题了
        visited[i][j] = true;
        let res = false;
        // 分别四个方向上进行实验
        for(const [dx,dy] of stepDirect){
            // 新的 i, j 就是往各自方向上相加
            let newI = i + dx, newJ = j + dy;
            // 这四个方向上走完之后，还在范围之内，没有越出边界
            if(newI >= 0 && newI < row && newJ >= 0 && newJ < col){
                // 而且不是走的之前的路径
                if(!visited[newI][newJ]){
                    if(dfs(newI,newJ,curIndex+1)){
                        res = true;
                        break;
                    }
                }
            }
        }
        // 回溯一步
        visited[i][j] = false;
        return res;
    }
    // 遍历这个二维数组，寻找起始点，有起始点的话进行DFS
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if(board[i][j] === word[0] && dfs(i,j,0)){
                return true;
            }
        }
    }
    return false;
};


/**
 * 文斌大大龙 【33】 篇
 * LeetCode 第 80 题
 * 删除有序数组中的重复项
 *
 * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
 *
 * 解题思路  双指针算法
 */

const removeDuplicates = function (nums) {
    let len = nums.length;
    // 如果长度小于 3 直接返回
    if(len < 3){
        return len;
    }
    // 定义慢指针
    let i = 1;
    // 进行遍历
    for (let j = 2; j < len; j++) {
        if(nums[i-1] !== nums[j]){
            i++;
            nums[i] = nums[j];
        }
    }
    // 返回的是长度，所以是下标位置 +1;
    return i+1;
}

/**
 * 文斌大大龙 【33】 篇
 * LeetCode第 81 题
 *
 * 搜索旋转排序数组
 * nums = [2,5,6,0,0,1,2], target = 0   输出 TRUE
 *
 * 解题思路 二分查找  （变相的二分查找，但是原理相同）
 */

const binarySearch = function(nums, target){
    let len = nums.length;
    if(len === 0){
        return false;
    }
    let [left, right] = [0, len - 1];
    while(left <= right){
        let pivot = Math.floor((left + right) / 2);
        if(nums[pivot] === target){
            return true;
        }
        if(nums[pivot] > nums[left]){
            if(nums[pivot] > target && target >= nums[left]){
                right = pivot - 1;
            }else{
                left = pivot + 1;
            }
        }else if(nums[pivot] < nums[right]){
            if(nums[pivot] < target && target <= nums[right]){
                left = pivot + 1;
            }else{
                right = pivot - 1;
            }
        }else {
            // 由于本体允许重复，所以这里是处理等于的情况
            if(nums[left] === nums[pivot]){
                left++;
            }
            if(nums[right] === nums[pivot]){
                right--;
            }
        }
    }
    return false;
}